import java.util.Arrays;
/*kmp算法
* */
class Solution {
    public int strStr(String haystack, String needle) {
        int len1=haystack.length();
        int len2=needle.length();
        if(len1==0&&len2==0){
            return 0;
        }
        int[] next=new int[len2];
        creatNext(next,needle);
        int i=0;
        int j=0;
        while(i<len1&&j<len2){

            if(j==-1||haystack.charAt(i)==needle.charAt(j)){
                i++;
                j++;
            }
            else{
                j=next[j];
            }
        }
        if(j>=len2){
            return i-j;
        }else{
            return -1;
        }
    }
    public void creatNext(int[] next,String needle){
        if(next.length==1){
            next[0]=-1;
            return;
        }
        next[0]=-1;
        next[1]=0;
        int k=0;
        int len=needle.length();
        int i=2;
        while(i<len){
            if(k==-1||needle.charAt(i-1)==needle.charAt(k)){
                next[i]=k+1;
                k=next[i];
                i++;

            }
            else{
                k=next[k];
            }
        }

    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        System.out.println(solution.strStr("a","a"));
    }
}